//https://leetcode.cn/problems/path-with-maximum-gold/
class Solution {
    int max;//最大黄金数目
    int row, col;
    boolean[][] check;//判断是否重复进入金矿
    int[][] grid;
    int[] dx, dy;//上下左右
    public int getMaximumGold(int[][] grid_) {
        grid = grid_;
        row = grid.length;
        col = grid[0].length;
        check = new boolean[row][col];
        dx = new int[]{1, -1,0 ,0};
        dy = new int[]{0, 0, -1, 1};
        int sum = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] != 0) {
                    check[i][j] = true;
                    sum += grid[i][j];
                    dfs(i, j, sum);
                    //回溯
                    check[i][j] = false;
                    sum -= grid[i][j];
                }
            }
        }
        return max;
    }
    public void dfs(int x, int y, int sum) {
        max = Math.max(max, sum);
        for(int k = 0; k < 4; k++) {
            int n = x + dx[k];
            int m = y + dy[k];
           if(n >= 0 && n < row && m >= 0 && m < col && !check[n][m] && grid[n][m] != 0) {
                sum += grid[n][m];
                check[n][m] = true;
                dfs(n, m, sum);
                //回溯
                check[n][m] = false;
                sum -= grid[n][m];
           }
        }
    }
}